⟸ Go Back ⟸

Exercise 2 (Homework 3).

(pumping lemma)

Counting as and bs is (in general) not regular

Show that the following languages are not regular.

1. \{w\in \{a,b\}^* \mid |w|_a = |w|_b\}
2. \{w\in \{a,b\}^* \mid |w|_a \geq |w|_b\}
3. \{w\in \{a,b\}^* \mid |w|_a \leq |w|_b\}
4. \{w\in \{a,b\}^* \mid |w|_a \neq |w|_b\}
5. \{w\in \{a,b,c\}^* \mid |w|_a \geq |w|_b \lor |w|_b\geq |w|_c \}
6. \{w\in \{a,b\}^* \mid |w|\in 3\mathbb N \Rightarrow |w|_a = |w|_b \}